/**
 * //你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的
 * //房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
 * //
 * // 给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
 * //
 * //
 * //
 * // 示例 1：
 * //
 * //
 * //输入：nums = [2,3,2]
 * //输出：3
 * //解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
 * //
 * //
 * // 示例 2：
 * //
 * //
 * //输入：nums = [1,2,3,1]
 * //输出：4
 * //解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
 * //     偷窃到的最高金额 = 1 + 3 = 4 。
 * //
 * // 示例 3：
 * //
 * //
 * //输入：nums = [1,2,3]
 * //输出：3
 * //
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * // 1 <= nums.length <= 100
 * // 0 <= nums[i] <= 1000
 * //
 * //
 * // Related Topics 数组 动态规划 👍 1131 👎 0
 */

package com.xixi.basicAlgroithms.dynamicPrograming;

public class ID00213HouseRobberIi {
    public static void main(String[] args) {
        Solution solution = new ID00213HouseRobberIi().new Solution();
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int rob(int[] nums) {

            int n = nums.length;
            //特殊情况
            if (n == 1) {
                return nums[0];
            } else if (n == 2) {
                return Math.max(nums[0], nums[1]);
            }


            //两种情况，因为 0 和 n-1只能偷一家，
            // 如果第0家可偷，n-1家就不可偷，可偷范围就是 0 - (n-2)
            //初始化前两家
            int first = nums[0], second = Math.max(nums[0], nums[1]);
            for (int i = 2; i < n - 1; ++i) {
                //表示当前家的最大化方案就是 i-2 的最大方案 + 偷当前家； 或者是 i-1的最大方案，不偷当前家 其中哪个大，当前家的最大方案就是哪个。
                int thisMax = Math.max(first + nums[i], second);
                first = second; //指针平移
                second = thisMax;
            }

            int rubFirst = second;

            // 如果第n-1家可偷，0家就不可偷， 剩下的可偷范围就是范围就变成 1 - (n-1)
            first = nums[1];
            second = Math.max(nums[1], nums[2]);
            for (int i = 3; i < n; ++i) {
                int thisMax = Math.max(first + nums[i], second);
                first = second; //指针平移
                second = thisMax;
            }

            int rubLast = second;


            // 最后的实际方案中，包含不包含这两家都无所谓，可能方案是 1 和 n-2都偷，就会导致两家都不能偷

            return Math.max(rubFirst, rubLast);


        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}